package problem763;

//763.划分字母区间
//https://leetcode.cn/problems/partition-labels/?envType=study-plan-v2&envId=top-100-liked

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>();
        int n = s.length();
        int i = 0;
        while(i < n) {
            int j = n-1;
            while(j > 0) {
                if(s.charAt(j) == s.charAt(i)) {
                    break;
                }
                j--;
            }
            int[] hash = new int[127];
            for(int k = i; k<=j; k++) {
                hash[s.charAt(k)]++;
            }
            int t = j;
            for(int k = j+1; k<n; k++) {
                if(hash[s.charAt(k)] != 0) {
                    for(int x = t+1; x <= k; x++){
                        hash[s.charAt(x)]++;
                    }
                    t = k;
                }
            }
            list.add(t-i+1);
            i = t+1;
        }
        return list;
    }
}